#include <stdio.h>
#include <stdlib.h>

// 请编写一个程序，在链表的第k个位置插入一个元素

typedef int ElemType; // 定义元素类型为int
typedef struct LNode
{
  ElemType data;      // 数据域：存储元素值
  struct LNode *next; // 指针域：指向下一个节点
} LNode, *LinkList;   // LNode为节点类型，LinkList为节点指针类型，用于表示链表的头指针

// 1. 初始化链表
/**
 * 初始化链表函数
 * @param L 指向链表头指针的指针，用于返回初始化后的链表头节点
 * 该函数动态分配一个头节点，并将头节点的next指针置为NULL
 */
void InitList(LinkList *L)
{
  // 为头节点分配内存空间
  *L = (LinkList)malloc(sizeof(LNode));
  // 检查内存是否分配成功
  if (*L == NULL)
  {
    printf("内存分配失败!\n");
    return;
  }
  // 将头节点的指针域置为空，表示这是一个空链表
  (*L)->next = NULL;
}
// 创建新节点
LNode *createNode(int val)
{
  LNode *newNode = (LNode *)malloc(sizeof(LNode));
  if (newNode == NULL)
  {
    printf("内存分配失败!\n");
    return NULL;
  }
  newNode->data = val;
  newNode->next = NULL;
  return newNode;
}

// 释放链表内存
void freeList(LNode *head)
{
  LNode *current = head;
  while (current != NULL)
  {
    LNode *temp = current;
    current = current->next;
    free(temp);
  }
}

/**
 * 打印链表中的所有元素
 * @param L 链表头指针
 */
void printList(LinkList L)
{
  // 检查链表是否存在
  if (L == NULL)
  {
    printf("链表不存在\n");
    return;
  }

  // 定义指针p并指向链表的第一个节点（头结点的下一个节点）
  LNode *p = L->next;
  printf("链表元素: ");
  while (p != NULL)
  {
    printf("%d ", p->data);
    // 移动指针p到下一个节点
    p = p->next;
  }
  printf("\n");
}

// 1. 按位置插入元素
int InsertElem(LinkList L, int pos, ElemType e)
{
  if (pos < 1)
    return 0; // 位置不合法（pos最小为1）

  LNode *p = L; // p从“头结点”开始
  int j = 0;    // 记录当前是第几个节点

  // 找到第pos-1个节点（插入位置的前驱节点）
  while (p != NULL && j < pos - 1)
  {
    p = p->next;
    j++;
  }

  if (p == NULL)
    return 0; // 位置超出链表范围

  // 为新节点分配内存并插入
  LNode *newNode = (LNode *)malloc(sizeof(LNode));
  if (newNode == NULL)
  {
    printf("Memory allocation failed!\n");
    return 0;
  }
  newNode->data = e;       // 新节点存入值
  newNode->next = p->next; // 新节点的next指向“前驱节点的原后继”
  p->next = newNode;       // 前驱节点的next指向新节点
  return 1;                // 插入成功
}

int main()
{
  int pos, e;
  int positions[] = {1, 3, 5, 7, 0, -1};
  LinkList L, L2; // L是链表头指针

  int values[] = {10, 20, 30, 40, 50, 60};
  int values2[] = {70, 80, 90, 100, 110, 120};
  // 初始化链表
  InitList(&L);

  int n = sizeof(values) / sizeof(values[0]);

  LNode *current = L;
  for (int i = 0; i < n; i++)
  {
    current->next = createNode(values[i]);
    current = current->next;
  }

  // ---------- 测试：插入元素 ----------
  printf("插入前链表：");
  printList(L);
  printf("请输入要插入的位置和元素（格式：位置 元素）：");
  scanf("%d %d", &pos, &e);
  if (InsertElem(L, pos, e))
  {
    printf("插入后链表：");
    printList(L);
  }
  else
  {
    printf("插入失败\n");
  }

  // 释放链表内存
  freeList(L);
  return 0;
}